package Graph;

import java.util.ArrayList;
import java.util.List;

public class Dijkstra {
    //迪克斯特拉 单源最短路径(起点只有一个)
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        v1.edges = List.of(new Edge(v2, 7),
                new Edge(v6, 14),
                new Edge(v3, 9)
        );
        v2.edges = List.of(new Edge(v4, 15)
        );

        v3.edges = List.of(new Edge(v6, 2),
                new Edge(v4, 11)
        );
        v6.edges = List.of(new Edge(v5, 9)
        );
        v4.edges = List.of(new Edge(v5, 6)
        );
        v5.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
        dijkstra(graph, v1);
    }

    private static void dijkstra(List<Vertex> graph, Vertex source) {
        //先将所有未访问的顶点加入到集合当中去
        ArrayList<Vertex> list = new ArrayList<Vertex>(graph);
        source.dist = 0;
        while (!list.isEmpty()) {
            //选取当前顶点
            Vertex curr = chooseMinDistVertex(list);
            //更新当前顶点邻居的距离
            updateneighboursDist(curr, list);
            //移除当前节点
            list.remove(curr);
        }
        graph.forEach(vertex -> {
            System.out.println(vertex.name + " " + vertex.dist);
        });
    }

    private static void updateneighboursDist(Vertex curr, ArrayList<Vertex> list) {
        curr.edges.forEach(temp -> {
            Vertex vertex = temp.linked;//邻居节点
            if (list.contains(vertex)) {
                int i = curr.dist + temp.weigth; //当前节点 加上边的权重
                if (vertex.dist > i) {  // 邻居节点的值 是否大于 当前节点加上边的权重
                    vertex.dist = i;  //如果大于就发现了更短的路径
                }
            }


        });

    }

    //返回当前节点邻居节点当中最小的节点
    private static Vertex chooseMinDistVertex(ArrayList<Vertex> list) {
        Vertex min = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            Vertex vertex = list.get(i);
            if (vertex.dist < min.dist) {
                min = vertex;
            }
        }
        return min;
    }


}
